package com.dmall.graph.shortest.path;

import com.dmall.graph.WeightedGraph;

import java.util.Arrays;

/**
 * Floyd算法，可以求所有点对的最短路径
 * @author: xiao1.wang
 * @date: 2022/8/31 23:07
 */
public class Floyd {

    private WeightedGraph G;
    private int[][] dis;
    private boolean hasNegCycle = false;

    public Floyd (WeightedGraph G) {
        this.G = G;
        this.dis = new int[G.V()][G.V()];
        for (int i = 0; i < G.V(); i++) {
            Arrays.fill(dis[i], Integer.MAX_VALUE);
        }

        for (int v = 0; v < G.V(); v++) {
            dis[v][v] = 0;
            for (int w : G.adj(v)) {
                dis[v][w] = G.getWeight(v, w);
            }
        }

        for (int t = 0; t < G.V(); t++) {
            for (int v = 0; v < G.V(); v++) {
                for (int w = 0; w < G.V(); w++) {
                    if (dis[v][t] != Integer.MAX_VALUE && dis[t][w] != Integer.MAX_VALUE && dis[v][t] + dis[t][w] < dis[v][w]) {
                        dis[v][w] = dis[v][t] + dis[t][w];
                    }
                }
            }
        }

        for (int v = 0; v < G.V(); v++) {
            if (dis[v][v] < 0) {
                hasNegCycle = true;
                break;
            }
        }
    }

    public boolean hasNegativeCycle() {
        return hasNegCycle;
    }

    public boolean isConnectedTo(int v, int w) {
        G.validateVertex(v);
        G.validateVertex(w);
        return dis[v][w] != Integer.MAX_VALUE;
    }

    public int distTo(int v, int w) {
        if (!isConnectedTo(v, w)) {
            throw new RuntimeException(String.format("No edge %d-%d", v, w));
        }
        if (hasNegativeCycle()) {
            throw new RuntimeException("exist negative cycle.");
        }
        return dis[v][w];
    }

    public static void main(String[] args) {
        String filename = BellmanFord.class.getClassLoader().getResource("wg.txt").getPath();
        WeightedGraph g = new WeightedGraph(filename);
        Floyd floyd = new Floyd(g);

        if(!floyd.hasNegativeCycle()){
            for(int v = 0; v < g.V(); v ++){
                for(int w = 0; w < g.V(); w ++)
                    System.out.print(floyd.distTo(v, w) + " ");
                System.out.println();
            }
        }
        else
            System.out.println("exist negative cycle.");
    }
}
